package Year21_Month11.day1101;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E>{
    public static class BTNode<E>{
        BTNode left;
        BTNode right;
        int data;

        public BTNode(int data){
            this.data = data;
        }
    }

   BTNode root;//构造根节点

    //构造二叉树
    public void creatBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;

        root = node1;
    }
    //前序遍历
    public void preOrder(BTNode root){
        if(root == null){
            return;
        }
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void  preOrder(){
        System.out.println("前序遍历:");
        preOrder(root);
    }

    //中序遍历
    public void inOrder(BTNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }
    public void inOrder(){
        System.out.println("中序遍历:");
        inOrder(root);
    }

    //后序遍历
    public void  postOrder(BTNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        inOrder(root.right);
        System.out.print(root.data + " ");
    }
    public void  postOrder(){
        System.out.println("后序遍历：");
        postOrder(root);
    }



    //获取结点个数
    public int size(BTNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }
    public int size(){
        return size(root);
    }
    //求叶子结点
    public int getLeafNodeCount(BTNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    public int getLeafNodeCount(){
        return getLeafNodeCount(root);
    }

    //求第k层结点个数
    public int getKLevelNodeCount(BTNode root,int k){
        if(root == null || k <= 0){
            return 0;
        }//先排除异常

        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
    }
    public int getKLevelNodeCount(int k){
        return getKLevelNodeCount(root,k);
    }

    //求树的高度
    public int getHeight(BTNode root){
        if(root == null){
            return 0;
        }
        return getHeight(root.left) > getHeight(root.right) ? 1 + getHeight(root.left) : 1 + getHeight(root.right);
    }
    public int getHeight(){
        return getHeight(root);
    }

    //判断值为value的节点是否存在
    public BTNode find(BTNode root, int val) {
        if(root == null){
            return null;
        }

        if(root.data == val){
            return root;
        }

        return find(root.right, val) != null ? find(root.right,val):find(root.left,val);
    }
    public BTNode find(int val) {
        return find(root,val);
    }
    //层序遍历第一种
    public void levelOrder(BTNode root){
        int a = getHeight(root);
        int i = 1;
        while(i <= a){
            getKLevelNode(root,i);
            i++;
        }
    }
    public void getKLevelNode(BTNode root,int k){
        if(root == null || k <= 0){
            return;
        }//先排除异常
        if(k != 1){
            getKLevelNode(root.left,k - 1);
            getKLevelNode(root.right,k - 1);
        }else{
            System.out.print(root.data + " ");
        }
    }
    //层序遍历第二种，为了区分，所以不传参数
    public void levelOrder(){
        if(root == null){
            return;
        }
        Queue<BTNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
                if(queue.peek().left != null){
                    queue.offer(queue.peek().left);
                }
                if(queue.peek().right != null){
                    queue.offer(queue.peek().right);
                }
                System.out.print(queue.poll().data + " ");
        }
    }

    public static void main(String[] args) {
        BinaryTree bT = new BinaryTree();
        bT.creatBinaryTree();
        bT.preOrder();//前序遍历
        System.out.println();
        bT.inOrder();//中序遍历
        System.out.println();
        bT.postOrder();//后序遍历
        //求结点个数
        System.out.println(bT.size());
        //求叶子结点个数
        System.out.println(bT.getLeafNodeCount());
        //求第k层结点个数
        System.out.println(bT.getKLevelNodeCount(3));
        //求树的高度
        System.out.println(bT.getHeight());
        //求值为value的结点是否存在
        System.out.println(bT.find(3).data);
        //层序遍历
        bT.levelOrder();
    }
}
